The problem can be found at the following link: Question Link
To find all the permutations of a given string s
, we can use a backtracking approach.
- The idea is to swap characters at different positions and recursively generate all possible permutations.
- We start with the first character
s[0]
and swap it with every other character in the string. Then, we recursively find all permutations of the remaining characters. - After generating all permutations, we sort the result vector to ensure the output is in lexicographically sorted order.
- Time Complexity:
O(N!)
, whereN
is the length of the input strings
. This is because there areN!
permutations possible for a string of lengthN
. - Auxiliary Space Complexity:
O(N!)
because theout
array will store all the permutations,
class Solution{
public:
vector<string> out;
void check(string &s, int i, int &n){
if(i == n){
out.push_back(s);
return;
}
for(int j = i; j < n; ++j){
swap(s[i], s[j]);
check(s, i+1, n);
swap(s[i], s[j]);
}
}
vector<string> permutation(string s){
int n = s.size();
check(s, 0, n);
sort(out.begin(), out.end());
return out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.